package Stack_Queue.queue.Impl;

import Stack_Queue.queue.Queue;

import java.util.NoSuchElementException;

//基于整型数组的循环队列
public class LoopQueue implements Queue<Integer> {
    private Integer[] data;
    //指向队列的队首
    private int head;
    //指向队列的队尾
    private int tail;
    //记录队列的元素个数
    private int size;

    //n为保存元素个数
    public LoopQueue(int n){
        //在循环队列中浪费一个空间不存储元素，来区分队列为空和为满
        data = new Integer[n + 1];
    }

    @Override
    public void offer(Integer val) {
        if (isFull()) {
            throw new ArrayIndexOutOfBoundsException("Queue is Full");
        }
        data[tail] = val;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public Integer poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is Empty!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        size--;
        return val;
    }

    @Override
    public Integer peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty!");
        }
        return data[head];
    }

    //取得队尾元素
    public Integer last() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty!");
        }
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        return data[lastIndex];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front - [");
        //取得元素最后一个元素下标
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail; ) {
            sb.append(data[i]);
            if (i != lastIndex) {
                sb.append("，");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] - tail");
        return sb.toString();
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    //判断队列是否已满
    public boolean isFull() {
        return (tail + 1) % data.length == head;
    }
}
